package com.wzl.day25;

import java.util.HashMap;
import java.util.Map;

/**
 * @ClassName Day25
 * @Description Day25
 * @Author wuzhilang
 * @Date 2020/4/25 22:05
 * @Version 1.0
 */
public class Day25 {
    //给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
//
// 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
//
//
//
// 示例:
//
// 给定 nums = [2, 7, 11, 15], target = 9
//
//因为 nums[0] + nums[1] = 2 + 7 = 9
//所以返回 [0, 1]
//
// Related Topics 数组 哈希表

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * [2,7,11,15]
         * 9
         * 先说下思路，用hash表来尝试一下。
         * 遍历一遍数组，map存储遍历过的数据，同时判断下有没有符合条件的数据，
         * 一旦发现就可以返回
         * 时间复杂度：O(n)， 我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。
         *
         * 空间复杂度：O(n)， 所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。
         * @param nums
         * @param target
         * @return
         */
        public int[] twoSum(int[] nums, int target) {
            Map<Integer, Integer> map = new HashMap<>();
            for (int i = 0; i < nums.length; i++) {

                int complement = target - nums[i];
                if (map.containsKey(complement)) {
                    return new int[] { map.get(complement), i };
                }
                map.put(nums[i], i);
            }
            throw new IllegalArgumentException("No two sum solution");
        }
    }
//leetcode submit region end(Prohibit modification and deletion)
}
